package 数据结构.链表;

import java.util.HashMap;

/**
 * @author Zhu
 * @Description
 * @create 2023-02-21
 */
public class JZ35复杂链表的复制 {

    //双指针

    /**
     * 1.对原链表的每个节点节点进行复制，并追加到原节点的后面；
     * 2.完成 1 操作之后，链表的奇数位置代表了原链表节点，链表的偶数位置代表了新链表节点，且每个原节点的 next 指针执行了对应的新节点。
     *   这时候，我们需要构造新链表的 random 指针关系，可以利用
     *      link[i + 1].random =  link[i].random.next
     *      i为奇数下标，含义为 新链表节点的 random 指针指向旧链表对应节点的 random 指针的下一个值；
     * 3.对链表进行拆分操作。
     *  */
    public RandomListNode Clone(RandomListNode pHead) {
//        step 1：遍历链表，对每个节点新建一个拷贝节点，并插入到该节点之后。
        //空节点直接返回
        if(pHead == null)
            return pHead;
        //添加一个头部节点
        RandomListNode cur = pHead;
        //遍历原始链表，开始复制
        while(cur != null){
            //拷贝节点
            RandomListNode clone = new RandomListNode(cur.label);
            //将新节点插入到被拷贝的节点后
            clone.next = cur.next;
            cur.next = clone;
            cur = clone.next;
        }
//        step 2：使用双指针再次遍历链表，两个指针每次都移动两步，一个指针遍历原始节点，一个指针遍历拷贝节点，
        //        拷贝节点的随机指针跟随原始节点，指向原始节点随机指针的下一位。
        cur = pHead;
        RandomListNode clone = pHead.next;
        RandomListNode res = pHead.next;
        //连接新链表的random节点
        while(cur != null){
            //跟随前一个连接random
            if(cur.random == null)
                clone.random = null;
            else
                //后一个节点才是拷贝的
                clone.random = cur.random.next;
            //cur.next必定不为空
            cur = cur.next.next;
            //检查末尾节点
            if(clone.next != null)
                clone = clone.next.next;
        }
        cur = pHead;
        clone = pHead.next;
//        step 3：再次使用双指针遍历链表，每次越过后一位相连，即拆分成两个链表。
        //拆分两个链表
        while(cur != null){
            //cur.next必定不为空
            cur.next = cur.next.next;
            cur = cur.next;
            //检查末尾节点
            if(clone.next != null)
                clone.next = clone.next.next;
            clone = clone.next;
        }
        return  res;
    }


    //哈希表
    public RandomListNode Clone2(RandomListNode pHead) {
//        step 1：建立哈希表，key为原始链表的节点，value为拷贝链表的节点。
        if (pHead == null)
            return pHead;
        RandomListNode res = new RandomListNode(0);
        HashMap<RandomListNode,RandomListNode> map = new HashMap<>();
        RandomListNode cur = pHead;
        RandomListNode pre = res;

//        step 2：遍历原始链表，依次拷贝每个节点，并连接指向后一个的指针，同时将原始链表节点与拷贝链表节点之间的映射关系加入哈希表。
        //遍历原始链表 开始复制
        while (cur != null){
            RandomListNode clone = new RandomListNode(cur.label);
            map.put(cur,clone);

            pre.next = clone;
            pre = pre.next;

            cur = cur.next;
        }
//        step 3：遍历哈希表，对于每个映射，拷贝节点的ramdom指针就指向哈希表中原始链表的random指针。
        //遍历哈希表
        for (HashMap.Entry<RandomListNode,RandomListNode> entry : map.entrySet()){
            //原始链表中的random为空
            if(entry.getKey().random == null)
                entry.getValue().random = null;
            else
                //将新链表的random指向哈希表中原始链表的random
                entry.getValue().random = map.get(entry.getKey().random);
        }
        return res.next;
    }
}
